Задача #R103B
Хасан и Прекрасно!
Вам дан массив \(a\) из \(n\) целых чисел \((a_1, a_2, ..., a_n)\) и целое число \(k\).
Вам необходимо выбрать непустой подмассив \(a_l, a_{l+1}, ..., a_r\) и выполнить одну из следующих операций:
1. Умножить все элементы подмассива на \(k\), то есть \(a_i := k \cdot a_i \quad (l \le i \le r)\).
2. Разделить все элементы подмассива на \(k\) с округлением вниз, то есть \(a_i := \left\lfloor \frac{a_i}{k} \right\rfloor \quad (l \le i \le r)\).
\(\lfloor x \rfloor\) обозначает наибольшее целое число, не превосходящее \(x\). Например, \(\lfloor 3.5 \rfloor = 3\) и \(\lfloor -3.5 \rfloor = -4\).
Среди всех подмассивов \(a\) определите максимально возможную сумму, которую можно получить, выбрав непустой подмассив и применив к нему одну из указанных операций.
В первой строке дано одно целое число:
\(t (1 \le t \le 10^4)\) – количество тестов.
В первой строке каждого теста содержатся два целых числа:
\(n\), \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(-10^9 \le k \le 10^9\)) – длина массива \(a\) и целое число \(k\).
Во второй строке каждого теста содержатся \(n\) целых чисел: \(a_1, a_2, ..., a_n\) (\(-10^4 \le a_1, a_2, ..., a_n \le 10^4\)) – массив \(a\).
Гарантируется, что сумма всех \(n\) по всем тестам не превышает \(2 \cdot 10^5\).
Для каждого теста выведите одно целое число: максимальная возможная сумма, которую можно получить, выбрав \(\bf{непустой}\) подмассив.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 1 10 5 10 5 10 5 3 10 -5 10 -5 10 3 4 1 -1 -2 |
40 60 4 |
В первом тесте оптимально выбрать весь массив, получив \(10 + 5 + 10 + 5 + 10 = 40\).
Во втором тесте оптимально выбрать весь массив и выполнить умножение \(3 \times 20 = 60\).
В третьем тесте оптимально выбрать подмассив \([1]\) и умножить на \(4\), таким образом ответ будет \(4\).
канал в Telegram, чтобы получать последние новости